An elementary approach to the problem of column selection in a rectangular matrix

摘要

The problem of extracting a well conditioned submatrix from any rectangularmatrix (with normalized columns) has been studied for some time in functionaland harmonic analysis; see\cite{BourgainTzafriri:IJM87,Tropp:StudiaMath08,Vershynin:IJM01} for methodsusing random column selection. More constructive approaches have been proposedrecently; see the recent contributions of\cite{SpielmanSrivastava:IJM12,Youssef:IMRN14}. The column selection problem weconsider in this paper is concerned with extracting a well conditionedsubmatrix, i.e. a matrix whose singular values all lie in$[1-\epsilon,1+\epsilon]$. We provide individual lower and upper bounds foreach singular value of the extracted matrix at the price of conceding only onelog factor in the number of columns, when compared to the RestrictedInvertibility Theorem of Bourgain and Tzafriri. Our method is fullyconstructive and the proof is short and elementary.